package com.joe.xl.demo.algorithm;

public class SortDemo {

    public static void main(String[] args) {
        // quicksort
        int i;
        int a[] = {35,25,40,30,24,60,50};
        System.out.println("before sort: ");
        for (i=0; i<a.length; i++)
            System.out.printf("%d ", a[i]);
        System.out.println();
        System.out.println("after");
        quicksort(a, 0, a.length-1);
        for (i=0; i<a.length; i++) {
            System.out.printf("%d ", a[i]);
        }

    }

    /***
     * 快速排序
     * @param a {35,25,40,30,24,60,50}
     * @param l
     * @param r
     */
    public static void quickSort(int[] a, int l, int r) {
        if(l < r) {
            int i, j, temp;
            i = l;
            j = r;
            temp = a[i];
            while (i < j) {
                while (i < j && a[j] > temp)
                    j--; // 从右向左找第一个小于x的数
                if (i < j)
                    a[i++] = a[j];
                while (i < j && a[i] < temp)
                    i++; // 从左向右找第一个大于x的数
                if (i < j)
                    a[j--] = a[i];
            }
            a[i] = temp;
            quickSort(a, l, i - 1); /* 递归调用 */
            quickSort(a, i + 1, r); /* 递归调用 */
        }
    }

    public static void quicksort(int[] arr, int left, int right) {
        if (left < right) {
            int i, j, temp;
            i = left;
            j = right;
            temp = arr[i];

            while (i < j) {
                while (i < j && arr[j] > temp)
                    j--;
                if (i < j)
                    arr[i++] = arr[j];
                while (i < j && arr[i] < temp)
                    i++;
                if (i < j)
                    arr[j--] = arr[i];
            }

            arr[i] = temp;
            quicksort(arr, left, i - 1);
            quicksort(arr, i + 1, right);
        }
    }
}
